As it is known in the art, imaging systems are used to translate a given input image to an output image. For example, a computer screen may register a given input image which is subsequently transferred to an output device, such as a printer. A problem may exist when transferring a multi-level chrominance or luminance (color or brightness) input image to an image generating output device because typical output devices are capable of displaying fewer chrominance or luminance levels for each pixel than are found in the input image.
Commonly, the effect of shading is achieved through digital halftoning, wherein each input level is simulated by varying the ratio of output chrominance or luminance levels in a small area of the screen. A drawback of digital halftoning is that visually sharp edges may be found in a resultant output image due to neighboring output pixels with different output chrominance or luminance levels. Dithering, which adds distinct integer values to the each pixel, was introduced to alleviate the sharp edges seen in halftoned output images. The conversion of an input image pixel array to an output image pixel array using dithering is well known in the art, see for example Robert A. Ulichneys Digital Halftoning, MIT Press, 1987, Chapter 5.
Ordered dithering uses a dither matrix whose elements are integer threshold values. The dither matrix is commonly smaller than the input image, and repeatedly laid down over the image in a periodic manner, thus tiling the input image. An example of a 4.times.4 dither matrix 250 tiled over a 16.times.16 input image 200 is shown in FIG. 1. Each element of the dither matrix 250 is an integer representing a threshold value. For example, with a bilevel output device, the threshold value determines whether or not an input pixel at that location will be turned "on", i.e. a black pixel or "off", i.e. a white pixel When the input pixel chrominance or luminance value is greater than the threshold value, the pixel is turned "on", if the chrominance or luminance value of the pixel is less than or equal to the threshold value, the pixel is turned "off". For example, if the 16.times.16 input image in FIG. 1 had 16 possible chrominance or luminance levels {0,1,2 . . . 15} for display on a bilevel output device, a given pixel 210 would be black only if the chrominance or luminance value of the original pixel of the input image 200 is greater than a 5, for example. Note that the highest threshold in the dither matrix is 14, thus ensuring that all input pixels with an chrominance or luminance level of 15 (the highest possible chrominance or luminance level in this example) will always be turned "on" in the output image. Because the dither matrix thresholds essentially determine which pixels of the input image will be displayed on the output device, the ordering of the threshold values in the dither matrix is related to the quality of the output image.
Various ordered dithering methods for arranging threshold values within a dither matrix have been developed. One problem with these ordered dithering methods is that regular patterns appear in the output images due to the tiling of the ordered dither matrix over the input image. This provides an output image which appears artificially processed. In addition, the ordered dither matrices tend to produce an output image with increased low frequency spatial characteristics. Low frequency spatial characteristics in an output image introduce residual visual artifacts which diminish the quality of the output image.
One approach to overcome this problem is the use of randomness to break up the rigid regularity of ordered dither. An example of the use of randomness is discussed by J. P. Allebach in 1976 in a paper entitled Random Quasi-Periodic Halftone Process, J. Opt. Soc. Am., vol. 66, pp. 909-917. Subsequent efforts by T. Mitsa and K. Parker are described in Digital Halftoning Using a Blue Noise Mask, Proc. SPIE, Image Proc. Algorithms and Techniques II, February 25-March 1, vol 1452, pp 47-56. Mitsa and Parker present a method to produce a "blue noise mask" ordered dither matrix for use in generating an output image with given spatial frequency domain characteristics, mimicking the "blue noise" patterns achieved with a compute intensive error diffusion algorithm described by Robert A. Ulichney in Digital Halftoning, Chapter 8, MIT Press, 1987. However, one problem with Mitsa and Parker's approach is that the complex process of generating the "blue noise mask" increases hardware complexity.